package main.old.new_2023.last.month_8;


import main.dataStruct.ListNode;
import main.dataStruct.TreeNode;

import java.util.*;

/**
 * @Description: todo 617. 合并二叉树
 * 给你两棵二叉树： root1 和 root2 。
 * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。
 * 合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
 * 返回合并后的二叉树。
 * 注意: 合并过程必须从两个树的根节点开始。
 *
 * todo 2208. 将数组和减半的最少操作次数
 * 给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
 * 请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
 *
 * todo 141. 环形链表
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
 * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 *
 * todo 142. 环形链表 II
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 * 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 * 不允许修改 链表。
 *
 * todo 143. 重排链表
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0814 {

    //重排链表
    public void reorderList(ListNode head) {
        //反转链表，然后组合
        ListNode reverseNode = reverseNode(head);
        while (reverseNode.next != null){
            head.next = reverseNode;
            reverseNode = reverseNode.next;
            head = head.next;
        }
    }
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    ListNode reverseNode(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseNode(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;

    }

    //环形链表 II
    public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        //哈希表能否完成
        HashSet<ListNode> listNodes = new HashSet<>();
        listNodes.add(head);
        ListNode next = head.next;
        while (next != null){
            if (listNodes.contains(next)){
                return next;
            }else {
                listNodes.add(next);
            }
            next = next.next;
        }
        return null;
    }

    //环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        //哈希表能否完成
        HashSet<ListNode> listNodes = new HashSet<>();
        listNodes.add(head);
        ListNode next = head.next;
        while (next != null){
            if (listNodes.contains(next)){
                return true;
            }else {
                listNodes.add(next);
            }
            next = next.next;
        }
        return false;
    }

    //将数组和减半的最少操作次数
    public int halveArray(int[] nums) {
        //优先队列 + 贪心算法
        PriorityQueue<Double> doubles = new PriorityQueue<>(Comparator.reverseOrder());
        double sum = 0;
        for (int num:nums){
            sum += num;
            doubles.add((double)num);
        }
        double subSum = 0;
        int count = 0;
        while (subSum < sum/2){
            Double max = doubles.poll();
            double temp = max / 2;
            subSum += max;
            doubles.offer(temp);
            count++;
        }
        return count;
    }

    //合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return dfs(root1,root2);
    }
    TreeNode dfs(TreeNode r1, TreeNode r2) {
        // 如果 r1和r2中，只要有一个是null，函数就直接返回
        if(r1==null || r2==null) {
            return r1==null? r2 : r1;
        }
        //让r1的值 等于  r1和r2的值累加，再递归的计算两颗树的左节点、右节点
        r1.val += r2.val;
        r1.left = dfs(r1.left,r2.left);
        r1.right = dfs(r1.right,r2.right);
        return r1;
    }

}
